package com.example.demo.leetcode.top100;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _34合并K个升序链表
 * @description
 * @date 2023/06/13 17:07
 * <p>
 * ******************************************************
 */
public class _34合并K个升序链表 {

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));

        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }

        while (!pq.isEmpty()) {
            ListNode curr = pq.poll();
            if (curr.next != null) {
                pq.offer(curr.next);
            }
            p.next = curr;
            p = p.next;

        }
        return dummy.next;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
